export interface CodeNode {
    data?: number;
    weight: number;
    left?: CodeNode;
    right?: CodeNode;
}

/**
 * @description 赫夫曼编码
 * @see 计算机的原码、反码和补码 https://blog.csdn.net/pyf09/article/details/110410235
 * @see ASCII对照表 http://ascii.911cha.com/
 */
export default class HuffmanCode {
    private static createNode(weight: number, data?: number) : CodeNode {
        return { data, weight };
    }

    /**
     * @description 字符串根据字节ASCII编码转换成节点
     * @param str 字符串
     * @returns CodeNode[]
     */
    public static getNodes(str: string): CodeNode[] {
        const charCountMap = new Map<number, number>();
        for (const s of str) {
            const char = s.charCodeAt(0);
            const count = charCountMap.get(char);
            if (count === undefined) {
                charCountMap.set(char, 1);
            } else {
                charCountMap.set(char, count + 1);
            }
        }

        const nodes: CodeNode[] = [];
        for (const [key, value] of charCountMap) {
            nodes.push(this.createNode(value, key));
        }
        return nodes;
    }

    public static toHuffmanTree(nodes: CodeNode[]) {
        while (nodes.length > 1) {
            nodes.sort((a, b) => b.weight - a.weight);
            const leftNode = nodes.pop() as CodeNode;
            const rightNode = nodes.pop() as CodeNode;
            const newNode: CodeNode = {
                weight: leftNode.weight + rightNode.weight,
                left: leftNode,
                right: rightNode
            };
            nodes.push(newNode);
        }
        return nodes[0];
    }

    public static front(node: CodeNode | undefined, res: CodeNode[] = []) {
        if (node !== undefined) {
            const { data, weight } = node;
            res.push({ data, weight });
            this.front(node.left, res);
            this.front(node.right, res)
        }
        return res;
    }

    /**
     * @description 生成赫夫曼编码，获取节点的所有叶子节点的赫夫编码
     * @example
     * - 空格(32) => 01
     * - a(97) => 100
     * - d(100) => 11000
     * @param {CodeNode} node 节点
     * @param {string} code 左子节点0，右子节点1，根节点为空字符
     * @returns Map<number, string>
     */
    public static getCodes(node: CodeNode | undefined, code: string = '', resStr: string = '', huffmap: Map<number, string> = new Map<number, string>()) {
        resStr += code;
        if (node !== undefined) {
            // 非叶子节点
            if (node.data === undefined) {
                // 向左递归
                this.getCodes(node.left, '0', resStr, huffmap);
                // 向右递归
                this.getCodes(node.right, '1', resStr, huffmap);
            }
            else {
                huffmap.set(node.data, resStr);
            }
        }
        return huffmap;
    }

    /**
     * @description 压缩赫夫曼码到字节数组
     * @param str 字符串
     * @param huffmap 赫夫曼码
     * @returns Uint8Array
     */
    public static zipStr(str: string, huffmap: Map<number, string>) {
        let str2 = '';
        for (const s of str) {
            const char = s.charCodeAt(0);
            str2 += huffmap.get(char);
        }
        // 统计按照8位数的字节有几个
        const len = Math.ceil(str2.length / 8);
        const huffmanCodeBytes = new Uint8Array(len);
        for (let i = 0; i < len; i++) {
            huffmanCodeBytes[i] = Number.parseInt(str2.substr(i * 8, 8), 2);
        }
        return huffmanCodeBytes;
    }

    /**
     * @description 解压数据
     * @example
     * 1. 将huffmanCodeBytes转成赫夫曼编码对应的二进制字符串
     */
    public static unZip() {
        // to do
    }
}